/*
	Simple implementation of "particle in cell"
	http://en.wikipedia.org/wiki/Particle-in-cell
	
	Original Author: collintmiller@gmail.com
	Date: November 2007
	
	"Particle-Man, Particle-Man, does whatever a particle can" - They Might Be Giants
	
	with box
	
	if # of nodes matching
		box.left < node.x < box.right
		box.top < node.y < box.bottom
	is > 1
	    add new level to tree
		split box into sub boxes
		repeat with each new box
	else
		add node to a tree
*/

var id = (function idMaker(prefix) {
	count = 0;
	return function makeId() {
		return prefix + "-" + count++;
	};
})("box");

function splitBox(box, splitBy) {
	splitBy = splitBy || 3;
	
	var stepWidth = (box.right - box.left) / splitBy,
		stepHeight = (box.bottom - box.top) / splitBy,
		boxes = [], flatBoxes = [], aBox,
		i, j, dimension;
		
	for (i = 0; i < splitBy; i++) {
		dimension = [];
		for (j = 0; j < splitBy; j++) {
				aBox = {id: id()};
				aBox.top = stepHeight * j + box.top;
			if (j !== splitBy) {
				aBox.bottom = stepHeight * (j+1) + box.top;
			}
			else {
				aBox.bottom = box.bottom;
			}
			dimension.push(aBox);
		}
		boxes.push(dimension);
	}
	
	for (i = 0; i < splitBy; i++) {
		for(j = 0; j < splitBy; j++) {
			aBox = boxes[j][i];
			aBox.left = stepWidth * j + box.left;
			if (j !== splitBy) {
				aBox.right = stepWidth * (j+1) + box.left;
			}
			else {
				aBox.right = box.right;
			}
			flatBoxes.push(aBox);
		}
	}
	return flatBoxes;
}

function nodesInBox(box, nodes) {
	var i, j, box, node,
		check = nodes,
		boxes = splitBox(box),
		length = boxes.length,
		jLength;
	
	box.children = [];
	box.mass = nodes.length;
	
	for (i = 0; i < length; i++) {
		aBox = boxes[i];
		nextCheck = [];
		inBox = [];
		jLength = check.length;
		for (j = 0; j < jLength; j++) {
			node = check[j];
			if (aBox.left <= node.x && node.x <= aBox.right && aBox.top <= node.y && node.y <= aBox.bottom) {
				inBox.push(node);
			}
			else {
				nextCheck.push(node);	
			}
		}
		
		check = nextCheck;
		
		if (inBox.length > 1) {
//			printBox(aBox);
			box.children.push(nodesInBox(aBox, inBox));
		}
		else if (inBox.length == 1) {
//			printBox(aBox);
			aBox.children = inBox;
			box.children.push(aBox);
		}
	}
	return box;
}

myBox = {
	id: id(),
	top: 0,
	bottom: 100,
	left: 0,
	right: 100
};

myNodes = [];
used = []; 

for (var i = 0; i < 64; i++) {
	var node = {
		x: Math.floor(Math.random()*100) + 1,
		y: Math.floor(Math.random()*100) + 1
	},
	unused = true;
	for (var j = 0; j < myNodes.length; j++) {
		used = myNodes[j];
		if(used.x == node.x && used.y == node.y) unused = false;
	}
	
	if (unused) {
		myNodes.push(node);
		printDot(node);
	}
	else {
		i--;
	}
}


function printDot(node) {
	var dot = document.createElement('div');
	dot.style.top = (node.y * 4) - 2 + 'px';
	dot.style.left = (node.x * 4) - 2 + 'px';
	dot.className = 'dot';
	document.body.appendChild(dot);
}

function printBox(box) {
	var _box = document.createElement('div');
	_box.style.top = box.top * 4 + 'px';
	_box.style.left = box.left * 4 + 'px';
	_box.style.width = (box.right - box.left) * 4 - 1 + 'px';
	_box.style.height = (box.bottom - box.top) * 4 - 1 + 'px';
	_box.id = box.id;
	_box.className = 'box';
	document.body.appendChild(_box);
}

function totalPosition(box, total) {
	var node, 
		slot,
		i, length = box.children.length;
	
	if (!total) total = [0, 0];

	if ((node = box.children[0]) && node.x) {
		total[0] += node.x;
		total[1] += node.y;
		return total;
	}
	for (i = 0; i < length; i++) {
		totalPosition(box.children[i], total);
	}
	
	return total;
}

function centerOfMass(box) {
	var positions = totalPosition(box),
		xy = {};
		xy.x = positions[0] / box.mass;
		xy.y = positions[1] / box.mass;
	return xy;
}

console.profile();
var quad = nodesInBox(myBox, myNodes);
var center = centerOfMass(quad);
console.profileEnd();